The development and application of rule engines is one branch of Artificial Intelligence (A.I.), which is a very broad research area that focuses on “making computers think like people.” Broadly speaking, a rule engine processes information by applying rules to data objects (also known as facts; or simply referred to as data). A rule is a logical construct for describing the operations, definitions, conditions, and/or constraints that apply to some predetermined data to achieve a goal. Various types of rule engines have been developed to evaluate and process rules. Conventionally, a rule engine implements a network to process rules and data objects, which are also referred to as facts. A network may include many different types of nodes, including, for example, object-type nodes, alpha nodes, left-input-adapter nodes, accumulate nodes, eval nodes, join nodes, not nodes, and terminal nodes, etc. Some conventional rule engines build Rete networks, and hence, are referred to as Rete rule engines.
Typically, data objects enter a network at the root node, from which they are propagated to any matching object-type nodes. From an object-type node, a data object is propagated to either an alpha node (if there is a literal constraint), a left-input-adapter node (if the data object is the left most object type for the rule), or a beta node (such as a join node). A set of facts matching a rule can be referred to as a tuple, which can be propagated from one node to another node.
A beta node has two inputs, unlike one-input nodes, such as object-type nodes and alpha nodes. A beta node can receive tuples in its left-input and data objects, or simply referred to as objects, in its right-input. Join nodes, not nodes, and exist nodes are some examples of beta nodes. All nodes may have one or more memories to store a reference to the data objects and tuples propagated to them, if any. For example, a beta node can have a left memory and a right memory associated with its left input and right input, respectively. The left-input-adapter node creates a tuple with a single data object and propagates the tuple created to the left input of the first beta node connected to the left-input-adapter node, where the tuple is placed in the left memory of the beta node and then join attempts are made with all the objects in the right memory of the beta node.
When another data object enters the right input of the join node, the data object is placed in the right memory of the join node and join attempts are made with all the tuples in the left memory of the join node. The tuples placed in the left memory of the join node are partially matched. If a join attempt is successful, the data object is added to the tuple, which is then propagated to the left input of the next node in the network. Such evaluation and propagation continue through other nodes down the network, if any, until the tuple reaches the terminal node. When the tuple reaches the terminal node, the tuple is fully matched. At the terminal node, an activation is created from the fully matched tuple and the corresponding rule. The activation is placed onto an agenda of the rule engine for potential firing or potential execution.
Conventional Rete networks does not explicitly define support for set operations, but several extensions have been developed in some rule engines to support them. For example, in Drools provided by Red Hat, Inc. of Raleigh, N.C., it is possible to define a rule that matches the sum of all items in a customer order by using the Accumulate Conditional Element (CE) as follows:
rule “Order statistics”when$total : Number ( ) from accumulate (OrderItem( $amt : amount ),sum( $amt ) )then// perform other operationsend
Although the previous approach works in some limited circumstances, it comes short when multiple calculations need to be executed for the same set of facts. For instance, if the previous rule would have to calculate not only the total, but also the minimum, average, and maximum item amount, then four (4) consecutive patterns would have to be used as follows:
rule “Order statistics”when$total : Number ( ) from accumulate (OrderItem( $amt : amount ), sum( $amt ) )$avg : Number ( ) from accumulate (OrderItem( $amt : amount ), average( $amt ) )$min : Number ( ) from accumulate (OrderItem( $amt : amount ), min( $amt ) )$max : Number ( ) from accumulate (OrderItem( $amt : amount ), max( $amt ) )then// perform other operations on $total, $avg, $min, and $maxend
This is not only verbose, but extremely inefficient. FIG. 1 shows the resulting Rete network for the above example. Note that the resulting Rete network 100 contains at least four accumulate nodes 111-114.